import collections
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        node = root
        stack = collections.deque()
        while node:
            stack.append(node)
            node = node.left
        n = len(stack)
        if n == 1:
            return 1
        total_sum = 2 ** (n - 1) - 1
        left_index = 1
        right_index = 2 ** (n - 1)
        depth = 0
        while right_index != left_index:
            new_stack = collections.deque()
            node = stack.popleft().right
            depth += 1
            while node:
                new_stack.append(node)
                node = node.left
            if len(new_stack) + depth == n:
                stack = new_stack
                left_index = (left_index + right_index + 1) // 2
            else:
                right_index = (left_index + right_index) // 2
        return total_sum + left_index



